package sort.insert;

import java.util.Arrays;

public class InsertSort {
	//记录量，记录选中的未排序元素
	public int temp;

	public int total;

	public int[] insertSort1(int[] array) {
		total = 0;
		//外循环，排序次数，从第二个元素开始
		for (int i = 1; i < array.length; i++) {
			//选择合适位置
			int j = i;
			//记录选中元素值
			temp = array[j];
			//位置选择循环判断条件
			while(j > 0) {
				//判断合适位置的前一个元素值与选中元素值
				if (array[j-1] > temp) {
					//元素后移
					array[j] = array[j-1];
					//选择位置前移
					j--;
				} else {
					//当array[i-1]<temp时，意味着位置合适，跳出循环
					break;
				}
			}
			total++;
			//选中元素值放入合适位置
			array[j] = temp;
		}
		return array;
	}


	public static void main(String[] args) {
		InsertSort test = new InsertSort();
		int array[];
		int array1[] = {1};
		int array2[] = {1,5,2,8,9,3};
		System.out.println("原数组：" + Arrays.toString(array1));
		System.out.println("原数组：" + Arrays.toString(array2));

		array = test.insertSort1(array1);
		System.out.println("SelectSort1：" + Arrays.toString(array));
		System.out.println("执行次数：" + test.total);

		array = test.insertSort1(array2);
		System.out.println("SelectSort1：" + Arrays.toString(array));
		System.out.println("执行次数：" + test.total);
	}

}
